package com.lw.leetcode.dp.c;

/**
 * Created with IntelliJ IDEA.
 * 1278. 分割回文串 III
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/29 15:52
 */
public class PalindromePartition {


    public static void main(String[] args) {
        PalindromePartition test = new PalindromePartition();

        // 1
//        String str = "abc";
//        int k = 2;

        // 0
        String str = "aabbc";
        int k = 3;

        // 0
//        String str = "leetcode";
//        int k = 8;

        int i = test.palindromePartition(str, k);
        System.out.println(i);
    }


    public int palindromePartition(String s, int k) {
        char[] chars = s.toCharArray();
        int length = s.length();
        int[][] items = new int[length][length];
        for (int i = length - 1; i >= 0; i--) {
            for (int j = i + 1; j < length; j++) {
                items[i][j] = items[i + 1][j - 1] + (chars[i] == chars[j] ? 0 : 1);
            }
        }
        int[][] arr = new int[length + 1][k + 1];
        for (int i = 1; i <= length; i++) {
            arr[i][1] = items[0][i - 1];
            for (int j = 2; j < Math.min(i, k + 1); j++) {
                int min = Integer.MAX_VALUE;
                for (int n = j - 1; n < i; n++) {
                    min = Math.min(min, arr[n][j - 1] + items[n][i - 1]);
                }
                arr[i][j] = min;
            }
        }
        return arr[length][k];
    }

}
